|
In the mathematical field of graph theory, an automorphism of a graph is a form of symmetry in which the graph is mapped onto itself while preserving the edge–vertex connectivity. Formally, an automorphism of a graph ''G'' = (''V'',''E'') is a permutation σ of the vertex set ''V'', such that the pair of vertices (''u'',''v'') form an edge if and only if the pair (σ(''u''),σ(''v'')) also form an edge. That is, it is a graph isomorphism from ''G'' to itself. Automorphisms may be defined in this way both for directed graphs and for undirected graphs. The composition of two automorphisms is another automorphism, and the set of automorphisms of a given graph, under the composition operation, forms a group, the automorphism group of the graph. In the opposite direction, by Frucht's theorem, all groups can be represented as the automorphism group of a connected graph – indeed, of a cubic graph.〔.〕〔.〕 ==Computational complexity== Constructing the automorphism group is at least as difficult (in terms of its computational complexity) as solving the graph isomorphism problem, determining whether two given graphs correspond vertex-for-vertex and edge-for-edge. For, ''G'' and ''H'' are isomorphic if and only if the disconnected graph formed by the disjoint union of graphs ''G'' and ''H'' has an automorphism that swaps the two components.〔.〕 In fact, just counting the automorphisms is polynomial-time equivalent to graph isomorphism〔R. Mathon, "A note on the graph isomorphism counting problem".〕 The graph automorphism problem is the problem of testing whether a graph has a nontrivial automorphism. It belongs to the class NP of computational complexity. Similar to the graph isomorphism problem, it is unknown whether it has a polynomial time algorithm or it is NP-complete.〔.〕 There is a polynomial time algorithm for solving the graph automorphism problem for graphs where vertex degrees are bounded by a constant.〔 The graph automorphism problem is polynomial-time many-one reducible to the graph isomorphism problem, but the converse reduction is unknown.〔R. Mathon, "A note on the graph isomorphism counting problem", ''Information Processing Letters,'' 8 (1979), pp. 131-132〕〔Jacobo Torán, "(On the hardness of graph isomorphism )", ''SIAM Journal on Computing,'' vol. 33 (2004), no. 5, pp. 1093-1108, 〕 By contrast, hardness is known when the automorphisms are constrained in a certain fashion; for instance, determining the existence of a fixed-point-free automorphism (an automorphism that fixes no vertex) is NP-complete, and the problem of counting such automorphisms is #P-complete.〔〔 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Graph automorphism」の詳細全文を読む スポンサード リンク
|